package Demo14;

import java.util.ArrayList;
import java.util.List;

/**
 * 找到字符串中所有的异位符
 * https://leetcode.cn/problems/find-all-anagrams-in-a-string/
 * 使用两个数组,来实现一个hash 来存储当前的字符串
 * 使用一个count 来统计当前的有效的字符长度
 * 当满足之后就添加到 list 当中
 */

class Solution {
    public List<Integer> findAnagrams(String ss, String pp) {
        // list 返回值表
        List<Integer> list = new ArrayList<>();
        // 将 ss 和 pp 字符串转换成 字符数组
        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();
        // 将pp 字符串的字符存储到hash2 当中
        int[] hash2 = new int[26];
        for(char ch:p) {
            hash2[ch - 'a']++;
        }
        int[] hash1 = new int[26];
        int m = p.length;// pp 字符串的长度
        // 遍历 s 字符数组
        for(int left = 0,right = 0,count = 0;right < s.length;right++) {
            char in = s[right];
            hash1[in - 'a']++;// 进入窗口
            if(hash1[in - 'a'] <= hash2[in - 'a']) count++;// 维护count
            if(right - left + 1 > m) {// 判断 当前滑动窗口范围 大于 pp 的长度了, 需要出队列
                char out = s[left];
                if(hash1[out- 'a']  <= hash2[out- 'a']) count--;// 维护当前count
                hash1[out- 'a']--;// 出窗口
                left++;
            }
            if (count == m) list.add(left);
        }
        return list;
    }
    public List<Integer> findAnagrams2(String ss, String pp) {
        List<Integer> list = new ArrayList<>();// 返回值数组
        // 将字符串转换成字符数组
        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();

        // 将p 放入到 hash 表当中
        int[] hash2 = new int[26];
        for(int i = 0; i < p.length;i++) {
            hash2[p[i] - 'a']++;
        }
        int[] hash1 = new int[26];
        int m = pp.length();
        // 使用双指针来实现数组
        for(int left = 0,right = 0,count = 0;right < s.length;right++) {
            char in = s[right];
            hash1[in - 'a']++; // 入窗口
            if(hash1[in - 'a'] <= hash2[in -'a']) count++;
            if(right - left + 1 > m ) {// 当前窗口长度大于 s.length
                char out = s[left];// 记录出窗口的字符
                if(hash1[out - 'a'] <= hash2[out - 'a']) count--;// 查看是否是有效字符,如果是就count--
                hash1[out - 'a']--;// 出窗口
                left++;// left 向右移
            }
            // 到这里, 当 有效字符的长度 和 pp 的长度一样, 那就说明是满足条件的,就添加到lsit当中
            if(m == count) {
                list.add(left);
            }
        }
        return list;
    }
}
class Demo {
    public static void main(String[] args) {
        Solution solution = new Solution();
        List list = solution.findAnagrams("cbaebabacd","abc");
        System.out.println(list);
    }
}